package java_1_13.singlelinked_list;

public class SinglelinkedList {
    //单链表-火车类
    //当前火车中车厢的节点个数（实际就是具体元素的个数）
    private int size;
    //火车头
    private Node head;
    /**
     *  1.在火车头部添加元素-实际就是添加一个车厢节点【头插法】
     */
    public void addFirst(int val){
        Node node=new Node(val);
        //判断火车头是否为空
        if(head==null){
            head=node;
        }else{//火车有车厢，把新车厢挂载到火车头部
            node.next=head;
            head=node;
        }
        size++;
    }

    /**
     * 2.index位置插入节点
     * @param index
     * @param val
     */
    public void addIndex(int index,int val) {
        //1.合法性2.边界index==0，调用头插3.中间位置插入：找前驱（循环）然后插入
        if (index < 0 || index > size) {
            System.out.println("add index illegal");
            return;
        }
        if (index == 0) {
            addFirst(val);
            return;
        }
        //此时插入节点不是头节点
        Node node = new Node(val);
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {//走到index位置的前一个，即找到了待插入节点的前驱
            prev = prev.next;
        }
        node.next = prev.next;
        prev.next = node;
        size++;
    }
    /**
     * 3.查：返回index位置元素
     */
    public int get(int index){
        if (rangeCheck(index)){
            Node node=head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            return node.val;
        }else{
            System.out.println("get index illegal");
            return -1;
        }
    }
    private boolean rangeCheck(int index){
        if(index<0||index>=size){
            return false;
        }
        return true;
    }
    /**
     * contains(int value):查询值为value的元素是否在单链表中存在
     */
    public boolean contains(int val){
        for(Node temp=head;temp!=null;temp=temp.next){
            if(temp.val==val){
                return true;
            }
        }
        return false;
    }
    /**
     * 4.改：set(int index,int newValue):修改index位置的值为newVale,返回改前的值
     */
    public int set(int index,int newVal){
        if(rangeCheck(index)){
            Node node=head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            int oldVal=node.val;
            node.val=newVal;
            return oldVal;
        }else{
            System.out.println("set index illegal");
            return -1;//不准确，万一原来的值就是-1呢？
        }
    }
    /**
     * 6.removeIndex(int index);删除链表中index节点
     */
    public void removeIndex(int index){
        if(rangeCheck(index)){
            if(index==0){
                Node temp=head;
                head=head.next;
                temp.next=null;
                size--;
            }else{
                //index不处于头节点处-找前驱
                Node prev=head;
                for (int i = 0; i < index - 1; i++) {
                    prev=prev.next;
                }
                Node cur=prev.next;
                prev.next=cur.next;
                cur.next=null;
                size--;
            }
        }else{
            System.out.println("remove index illegal");
            return;
        }
    }
    public void removeFirst(){
        removeIndex(0);
    }
    public void removeLast(){
        removeIndex(size-1);
    }
    /**
     * 7.removeValueOnce(int val):删除单链表中第一个值为val的节点
     */
    public void removeValOnce(int val){
        //先判断头节点
        if(head.val==val){
            Node node=head;
            head=head.next;
            node.next=null;
            size--;
        }else{
            //head一定不是待删除结点
            Node prev=head;
            while(prev.next!=null){
                if(prev.next.val==val){
                    Node cur=prev.next;
                    prev.next=cur.next;
                    cur.next=null;
                    size--;
                    return;
                }
                prev=prev.next;
            }
        }
    }
    /**
     * 8.removeValueAll(int val):删除单链表中所有值为val的节点
     */
    public void removeValAll(int val){
        //判断头节点
        while(head!=null&&head.val==val){
            head=head.next;
            size--;
        }
        if(head==null){
            return;
        }else{
            //head一定不是待删除结点并且链表中还有节点
            Node prev=head;
            while(prev.next!=null){
                if(prev.next.val==val){
                    prev.next=prev.next.next;
                    size--;
                }else{
                    prev=prev.next;
                }
            }
        }
    }
    /**
     * 遍历打印单链表
     */
    public String toString(){
        String ret="";
        Node node=head;
        while(node!=null){
            ret+=node.val;
            ret+="->";
            node=node.next;
        }
        ret+="NULL";
        return ret;
    }
}
class Node{
    //车厢类
    // 存储具体数值
    int val;
    //存储下一节车厢地址
    Node next;
    public Node(int val) {
        this.val = val;
    }
}